/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Tri;

import java.util.ArrayList;
import metier.ListPersonne;
import metier.Personne;

/**
 *Classe permettant de faire tous les différents tri nécessaire pour le projet
 */
public class TriRapide {

     
/**
 *fonction triant la liste de personne par leur degré de célébrité
 * utilise un tri quickSort
 * 
 * paramètres : list : la liste de personne du réseau
 *              first et last : des nombres pris au hasard pour pouvoir placer le pivot ensuite 
 * 
 */
    
     public static void quickSortDegree (ArrayList <Personne> list, int first, int last)
    {
        int g = first, h = last;

        int midIndex = (first + last) / 2;
        int dividingValue = list.get(midIndex).getDegre_celeb();
        do
        {
            while (list.get(g).getDegre_celeb() < dividingValue) g++;
            while (list.get(h).getDegre_celeb() > dividingValue) h--;
            if (g <= h)
            {
                //swap(list[g], list[h]);
                swap(list,g,h);
                g++;
                h--;
            }
        }

        while (g < h);

        if (h > first) quickSortDegree (list,first,h);
        if (g < last) quickSortDegree (list,g,last);
    }
     
/**
 *fonction interchangeant deux individus
 * 
 * paramètres : list : la liste de personne du réseau
 *              g : la première personne à changer de place
 *              h : la deuxième personne à changer de place
 * 
 */

    public static void swap (ArrayList <Personne> list, int g, int h)
    {
       Personne temp = list.get(g);
        list.set(g, list.get(h));
        list.set(h, temp);

    }
      
/**
 *fonction triant la liste de personne par leur nom
 * utilise un tri quickSort
 * 
 * paramètres : tableau : la liste de personne du réseau
 *              début et fin : des nombres pris au hasard pour pouvoir placer le pivot ensuite 
 * 
 */
    
    public static void quickSortString(ArrayList <Personne> tableau, int debut, int fin) {
        try {
            int gauche = debut;
            int droite = fin;
            String pivot = tableau.get(debut).getNom();
            /*
             * Si le tableau est de longueur nulle, il n'y a rien à faire.
             */
            if (debut >= fin) {

                return;
            }
            /*
             * Sinon, on parcourt le tableau, une fois de droite à gauche, et
             * une autre de gauche à droite, à la recherche d'éléments mal
             * placés, que l'on permute. Si les deux parcours se croisent, on
             * arrête.
             */
            while (true) {
                while ((tableau.get(droite).getNom()).compareTo(pivot) > 0) {
                    droite--;
                }
                while ((tableau.get(gauche).getNom()).compareTo(pivot) < 0) {
                    gauche++;
                }

                if (gauche < droite) {
                    swap(tableau, gauche, droite);
                } else {
                    break;
                }
            }
            /*
             * on trie maintenant tous les éléments se trouvant à droite du
             * pivot et ceux se trouvant à gauche du pivot
             */
            quickSortString(tableau, debut, droite - 1);
            quickSortString(tableau, droite + 1, fin);
        } catch (Exception e) {
            System.out.println("ERROR : "+e.getMessage());

        }
    }

/*============================
     * Ancien Tri non optimisé
     * ================================
     * 
     * 
    
    public static void echangerInt(int[] tableau, int a, int b) {
        int temp;
        temp = tableau[a];
        tableau[a] = tableau[b];
        tableau[b] = temp;
    }
    public static void quick_srt(Personne array[], int low, int n) {
        try{
        int lo = low;
        int hi = n;
        if (lo >= n) {
            return;
        }
        int mid = array[(lo + hi) / 2].getDegre_celeb();
        while (lo < hi) {
            while (lo < hi && array[lo].getDegre_celeb() < mid) {
                lo++;                       
            }
            while (lo < hi && array[hi].getDegre_celeb() > mid) {
                hi--;
            }
            if (lo < hi) {
                Personne T = array[lo];
                array[lo] = array[hi];
                array[hi] = T;
                hi--;
            }
        }
        if (hi < lo) {
            int T = hi;
            hi = lo;
            lo = T; 
        }
        quick_srt(array, low, lo);
        quick_srt(array, lo == low ? lo + 1 : lo, n);
    }catch(Exception e){
                    System.out.println("ERROR : "+e.getMessage());

    }  
}  
    
    */
    
/**
 *fonction triant la liste de personne par leur pseudo
 * utilise un tri quickSort
 * 
 * paramètres : list : la liste de personne du réseau
 *              first et last : des nombres pris au hasard pour pouvoir placer le pivot ensuite 
 * 
 */
    public static void quickSortPseudo (ArrayList <Personne> list, int first, int last)
    {
        try {
            int g = first, h = last;

            int midIndex = (first + last) / 2;
            int dividingValue = list.get(midIndex).getPseudo();
            do
            {
                while (list.get(g).getPseudo() < dividingValue) g++;
                while (list.get(h).getPseudo() > dividingValue) h--;
                if (g <= h)
                {
                    //swap(list[g], list[h]);
                    swap(list,g,h);
                    g++;
                    h--;
                }
            }

            while (g < h);

            if (h > first) quickSortPseudo(list,first,h);
            if (g < last) quickSortPseudo(list,g,last);
        } catch (Exception e) {
            System.out.println("ERROR : "+e.getMessage());

        }
    }
}
